package com.hqq.exercise.tree;

/**
 * PostTraversal 后序遍历搜索二叉树
 * 题目描述:
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。是则返回true，否则返回false。
 * 思路:
 * 对于一个初始数组 最后一个元素是根节点，它之前的元素可以分成两部分，一部分比它小,一部分比它大
 * 对于这两部分 又可以分为根节点和两部分 因此可以用递归来实现
 * Created by heqianqian on 2017/8/13.
 */
public class PostTraversal {

    public static boolean isPostOrder(int[] result) {
        if (result == null) {
            return false;
        }
        return isPostOrder(result, result.length);
    }

    private static boolean isPostOrder(int[] result, int length) {
        if (result == null || length < 0) {
            return false;
        }
        int root = result[length - 1];//后序遍历的最后一个节点是根节点
        int leftIndex = 0;
        //左子树都小于根节点
        while (result[leftIndex] < root) {//找到左子树的根节点
            leftIndex++;
        }
        int rightIndex = leftIndex + 1;
        //右子树都大于根节点
        for (; rightIndex < length - 1; rightIndex++) {
            if (result[rightIndex] < root) {//出口条件 如果右子树中存在比根节点小的树 那么不符合后序搜索二叉树的规则 返回false
                return false;
            }
        }
        //判断左子树是不是二叉树
        boolean left = true;
        if (leftIndex > 0) {
            left = isPostOrder(result, leftIndex);//递归后序遍历左子树
        }
        //判断右子树是不是二叉树
        boolean right = true;
        if (leftIndex < length - 1) {
            right = isPostOrder(result, length - leftIndex - 1);//递归后序遍历右子树
        }
        return (left && right);
    }
}
